1. Field of the Invention
The present invention relates to a system and method for message exchanges which minimize network overhead and offers fast determination of Coordinates of a node in a Wireless Communication Network. Specifically, the system and method controls a node to exchange small, structured messages with one or more reference nodes requesting the Coordinates of the reference node, which are then used in periodic evaluations of time of flight messages from that reference node for determination of Coordinates of the node.
2. Description of the Related Art
Wireless communication networks, such as mobile wireless telephone networks, have become increasingly prevalent over the past decade. These wireless communications networks are commonly referred to as “cellular networks”, because the network infrastructure is arranged to divide the service area into a plurality of regions called “cells”. A terrestrial cellular network includes a plurality of interconnected base stations, or base nodes, that are distributed geographically at designated locations throughout the service area. Each base node includes one or more transceivers that are capable of transmitting and receiving electromagnetic signals, such as radio frequency (RF) communications signals, to and from mobile user nodes, such as wireless telephones, located within the coverage area. The communications signals include, for example, voice data that has been modulated according to a desired modulation technique and transmitted as data packets. As can be appreciated by one skilled in the art, network nodes transmit and receive data packet communications in a multiplexed format, such as time-division multiple access (TDMA) format, code-division multiple access (CDMA) format, or frequency-division multiple access (FDMA) format, which enables a single transceiver at a first node to communicate simultaneously with several other nodes in its coverage area.
In recent years, a type of mobile communications network known as an “ad-hoc” network has been developed. In this type of network, each mobile node is capable of operating as a base station or router for the other mobile nodes, thus eliminating the need for a fixed infrastructure of base stations. Details of an ad-hoc network are set forth in U.S. Pat. No. 5,943,322 to Mayor, the entire content of which is incorporated herein by reference.
More sophisticated ad-hoc networks are also being developed which, in addition to enabling mobile nodes to communicate with each other as in a conventional ad-hoc network, further enable the mobile nodes to access a fixed network and thus communicate with other mobile nodes, such as those on the public switched telephone network (PSTN), and on other networks such as the Internet. Details of these advanced types of ad-hoc networks are described in U.S. pat. No. 7,072,650 entitled “Ad Hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks”, issued on Jul. 4, 2006, in U.S. pat. No. 6,807,165 “Time Division Protocol for an Ad-Hoc, Peer-to-Peer Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel”, issued on Oct. 19, 2004, and in U.S. pat. No. 6,873,839 entitled “Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System”, issued on Mar. 29, 2005, the entire content of each being incorporated herein by reference.
In either conventional wireless communications networks, or in ad-hoc wireless communications networks, it may be necessary or desirable for a mobile node to be capable of knowing or determining a relative or absolute geographic location or position. As known to those skilled in the art, this can be achieved through the use of a number of technologies. These technologies can include cell identification, combined with Round Trip Time (RTT), Timing Advance (TA) and Measured Signal level (RX level), Time Difference of Arrival (TDOA) and Angle Of Arrival (AOA) techniques, the details of which can be appreciated by one skilled in the art. Another available technology can use cellular signal timing based methods for code division multiple access (CDMA) and wideband code division multiple access (WCDMA). Yet another technology can use Global Positioning System (GPS) techniques.
Despite the fact that the GPS technique has been in use for a considerable period of time and most of the world's navigation relies on this technique, the GPS technique is very susceptible to errors in measurement. Therefore, the GPS technique is capable of providing location determination results with very high accuracy only after performing a relatively large number of measurements to remove such errors. Other tests also demonstrate that the GPS technique is unsuitable for those terrestrial-based networks operating in locations where the number of simultaneous visible satellites is too small or not existent, like in underground tunnels, inside buildings, or in urban “canyons”.
To overcome the above issues with determining location information, ad-hoc networks are being developed which do not require either the use of satellites or a centralized computing facility for determining location information. Further details of such ad-hoc networks are described in U.S. Pat. No. 6,728,545 entitled “A System and Method for Computing the Location of a Mobile Terminal in a Wireless Communications Network”, filed on Nov. 16, 2001, the entire content of which is being incorporated herein by reference. Additionally, ad-hoc networks can be developed which utilize non-fixed, or movable infrastructure components. Further details of networks using movable access points and repeaters for minimizing coverage and capacity constraints are described in U.S. patent Publication No. 20030091010A1 entitled “Movable Access Points and Repeaters for Minimizing Coverage and Capacity Constraints in a Wireless Communications Network and a Method for Using the Same”, filed Aug. 15, 2001, the entire content of which is being incorporated herein by reference.
The publications discussed above generally relate to mobile networks that connect to a permanent fixed network. However, as can be appreciated from the information referenced above, wireless ad-hoc networks do not necessarily have the same requirements, and include numerous communication issues that must be addressed in position determination.
In a typical wireless communication network, positions or Coordinates are typically found in the following manner. Reference nodes periodically transmit packets containing their Coordinates, the size of the packet can vary depending upon the accuracy desired. The Subscriber Devices receive and note the location of the reference nodes. Subscriber Devices then do specific time of flight measurements on these reference nodes at a regular interval, depending upon the accuracy desired. Coordinates of the Subscriber Devices are then determined by using the distance from various reference nodes thorough time of flight measurements, and the Coordinates of the reference nodes.
In such systems and methods, Coordinates of the reference nodes must be transmitted at a periodic rate. These are typically sent along with some periodic message like Hello Message or Neighbor Advertisement. If no such message is available, a special message needs to be sent at some periodic interval. However, periodic broadcast messages are expensive in a wireless ad-hoc network, especially where multi-channel MAC protocols are used, as it prevents other unicast messages from occurring during that period and hence, affects the number of devices present in an area (i.e. scalability). This information is particularly wasteful if few Subscriber Devices are using “Location Service”. Not all subscribers want or pay for, such location services.
Additionally, the information about the location of fixed nodes does not typically change with time, that is fixed nodes will keep on transmitting the same coordinates all the time, simply consuming bandwidth and adding overhead. Therefore, the overhead can be reduced by increasing the interval between consecutive broadcast messages. However this increases the time intervals between which the Subscriber Device can determine its Coordinates. This is highly undesirable in a mobile ad-hoc network where nodes move at a fast speed.
Accordingly, a need exists for a system and method of location determination which reduces the required overhead on the network, while also improving the speed at which the Coordinates are determined.